<?php

class Node {

    public $val;
    public $next = null;

    public function __construct($val)
    {
        $this->val = $val;
    }

    public function setNext($node)
    {
        $this->next = $node;
        return $this;
    }
}

class LinkedList {

    private $head;
    private $size;

    public function __construct()
    {
        $this->head = null;
        $this->size = 0;
    }

    public function get(int $index)
    {
        if ($index < 1 || $index > $this->size) {
            throw new Exception('index is error');
        }

        $curr = $this->head;
        for ($i = 1; $i < $index; $i++) {
            $curr = $curr->next;
        }

        return $curr->val;
    }


    /**
     * 链表头部添加元素
     * @param Node $node
     */
    public function addFirst(Node $node)
    {
        $node->next = $this->head;
        $this->head = $node;
        //$this->head = $node->setNext($this->head);  等价上面代码
        $this->size++;
    }

    /**
     * 链表尾部添加元素
     * @param Node $node
     * @throws Exception
     */
    public function addLast(Node $node)
    {
        $this->add($node, $this->size);
    }

    /**
     * 链表中间插入元素
     * @param Node $node
     * @param int $index
     * @throws Exception
     */
    public function add(Node $node, int $index)
    {
        if ($index < 0 || $index > $this->size) {
            throw new Exception('index is error');
        }

        if ($index === 0) {
            $this->addFirst($node);
            return;
        }

        $curr = $this->head;
        for ($i = 1; $i < $index; $i++) {
            $curr = $curr->next;
        }

        $node->next = $curr->next;
        $curr->next = $node;

        $this->size++;
    }

    public function update(int $index, $value)
    {
        if ($index < 0 || $index > $this->size) {
            throw new Exception('index is error');
        }

        $curr = $this->head;
        for ($i = 1; $i < $index; $i++) {
            $curr = $curr->next;
        }

        $curr->val = $value;
        return true;
    }

    public function removeFirst()
    {
        if ($this->head === null) {
            return null;
        }

        $removedNode = $this->head;
        $this->head = $this->head->next;
        $removedNode->next = null;
        $this->size--;
        return $removedNode->val;
    }

    public function removeLast()
    {
        if ($this->head === null) {
            return null;
        }

        if ($this->size === 1) {
            return $this->removeFirst();
        }

        $prev = $this->head;
        $curr = $prev->next;
        while ($curr->next !== null) {
            $prev = $curr;
            $curr = $curr->next;
        }

        $prev->next = null;
        $this->size--;
        return $curr->val;
    }

    public function remove(int $index)
    {
        if ($index < 1 || $index > $this->size) {
            throw new Exception('index is error');
        }

        if ($index === 1) {
            $this->head = $this->head->next;
            return true;
        }

        $prevNode = $this->head;
        $currNode = $this->head->next;
        for ($i = 1; $i < $index; $i++) {
            $prevNode = $prevNode->next;
            $currNode = $currNode->next;
        }

        $prevNode->next = $currNode->next;
        return true;
    }

    public function contains($val)
    {
        $curr = $this->head;
        while ($curr !== null) {
            if ($curr->val == $val) {
                return true;
            }
            $curr = $curr->next;
        }
        return false;
    }

    /**
     * 返回链表长度
     * @return int
     */
    public function len():int
    {
        return $this->size;
    }

    public function print()
    {
        $curr = $this->head;
        $str = '';
        while ($curr !== null) {
            $str .= $curr->val . '->';
            $curr = $curr->next;
        }

        $str = preg_replace('/->$/', '', $str);
        print_r($str . "\r\n");
    }

}

$link = new LinkedList();
$link->addFirst(new Node(1));
$link->addFirst(new Node(5));
$link->addFirst(new Node(3));
//$link->add(new Node(6), 2);
$link->print();
$link->addLast(new Node(6));
$link->addLast(new Node(7));
$link->print();
//echo $link->removeFirst();
//echo $link->removeFirst();
//echo $link->removeLast();
//echo $link->removeLast();
//var_dump($link->contains(0));
//echo $link->get(2);
$link->update(1, 10);
$link->print();





